﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ListNode.LinkedListIntersect
{
    class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }
    //=============================== 力扣07 链表相交
    //给定两个单向链表，判定他们是否相交并返回交点。
    //相交的定义基于节点的引用，而不是基于节点的值。
    //简单来说就是求两个链表交点节点的指针。
    class LinkedListIntersect
    {
        public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
        {
            ListNode curA = headA;
            ListNode curB = headB;
            int lenA = 0, lenB = 0;
            while (curA != null)
            {//求链表A的长度
                lenA++;
                curA = curA.next;
            }
            while (curB != null)
            {//求链表B的长度
                lenB++;
                curB = curB.next;
            }
            curA = headA;
            curB = headB;
            //让curA为最长链表的头，lenA为其长度
            if (lenB > lenA)
            {
                int tmpLen = lenA;
                lenA = lenB;
                lenB = tmpLen;
                ListNode temNode = curA;
                curA = curB;
                curB = temNode;
            }
            //求长度差
            int gap = lenA - lenB;
            //让curA和curB在同一起点上（末尾位置对齐）
            while (gap-- > 0)
            {
                curA = curA.next;
            }
            while (curA != null)
            {
                if (curA == curB)
                    return curA;
                curA = curA.next;
                curB = curB.next;
            }
            return null;
        }
    }
}
